package queue

import (
	"algorithm-go/link"
	"errors"
)

const minQueueLen = 16

type element interface {
	int
}

type Queue[T element] struct {
	buf               []T
	head, tail, count int
}

func New[T element]() *Queue[T] {

	return &Queue[T]{
		buf: make([]T, minQueueLen),
	}
}

func (queue *Queue[T]) Length() int {
	return queue.count
}

func (queue *Queue[T]) resize() {

	// 扩缩容slice，调整缓冲区长度为元素实际数量的狼狈
	newBuf := make([]T, queue.count<<1)
	// 拷贝数据 buf 是一个循环数组，因此当tail > head时拷贝的是中间部分
	if queue.tail > queue.head {
		copy(newBuf, queue.buf[queue.head:queue.tail])
	} else {
		// 当tail < head 时拷贝的是两头
		n := copy(newBuf, queue.buf[queue.head:])
		copy(newBuf[n:], queue.buf[:queue.tail])
	}
	// 重置队列
	queue.head = 0
	queue.tail = queue.count
	queue.buf = newBuf
}

func (queue *Queue[T]) Add(elem T) {

	// 队列已满则需要扩容
	if queue.count == len(queue.buf) {
		queue.resize()
	}
	queue.buf[queue.tail] = elem
	// 更新队列尾部 这是个结论不妨记下来即可
	queue.tail = (queue.tail + 1) & (len(queue.buf) - 1)
	queue.count++
}

func (queue *Queue[T]) Peek() T {
	if queue.count < 1 {
		panic("queue: Peek() called on empty queue")
	}

	return queue.buf[queue.head]
}

func (queue *Queue[T]) Get(i int) T {
	if i < 0 {
		// i 小于0相当于从尾部往前找
		i += queue.count
	}

	if i < 0 || i >= queue.count {
		panic("queue: Get() called with index out of range")
	}

	// 获取第几个元素，头指针往前 i 个 & 队列长度加1
	return queue.buf[(queue.head+i)&(len(queue.buf)-1)]
}

func (queue *Queue[T]) Remove() T {
	// 取出队列头部元素
	if queue.count <= 0 {
		panic("Queue: Remove() called on empty queue ")
	}

	ret := queue.buf[queue.head]
	queue.buf[queue.head] = 0
	// 重新计算队列头
	queue.head = (queue.head + 1) & (len(queue.buf) - 1)
	queue.count--
	// 缩容，当队列缓冲区长度大于最小值，且队列中实际元素数量为队列缓冲区长度4倍时
	if len(queue.buf) > minQueueLen && (queue.count<<2) == len(queue.buf) {
		queue.resize()
	}
	return ret
}

// CircularQueue 基于数组实现的循环链表, 循环链表判定满的条件是 (tail + 1)%n = head,记住即可，相关数学推导可省略
// 循环链表需要留出一个节点空闲
type CircularQueue struct {
	data [16]int
	tail int
	head int
}

// enqueue 入队操作
func (queue *CircularQueue) enqueue(element int) (err error) {

	if (queue.tail+1)%16 == queue.head {
		return errors.New("队列已经满了")
	}

	queue.data[queue.tail] = element
	queue.tail = (queue.tail + 1) % 16

	return nil
}

// dequeue 出队操作
func (queue *CircularQueue) dequeue() (result int, err error) {

	if queue.head == queue.tail {
		return 0, errors.New("队列已空")
	}
	result = queue.data[queue.head]
	queue.head = (queue.head + 1) % 16
	return result, nil
}

// LinkedQueue 基于链表实现的队列
type LinkedQueue struct {
	head *link.Node
	tail *link.Node
}

// Enqueue 入队操作
func (queue *LinkedQueue) Enqueue(element int) {

	// 这里暂不处理队列满了的情况
	node := &link.Node{Data: element}
	if queue.tail == nil {
		queue.tail = node
	} else {
		queue.tail.Next = node
		queue.tail = queue.tail.Next
	}
	if queue.head == nil {
		queue.head = node
	}
}

// dequeue 出队操作
func (queue *LinkedQueue) dequeue() (element int, err error) {

	if queue.head == nil {
		return 0, errors.New("队列已经空了")
	}
	result := queue.head.Data
	queue.head = queue.head.Next
	return result, nil
}

// ArrayQueue 基于数组实现的队列
type ArrayQueue struct {
	data [16]int

	head int
	tail int
}

// enqueue 数据入队
func (queue *ArrayQueue) enqueue(element int) (err error) {

	// 队列满了
	if queue.head == 0 && queue.tail == 16 {
		return errors.New("队列已经满了")
	}
	// 队列尾部已经触及数组最后
	if queue.tail == 16 {
		for index := queue.head; index < 16; index++ {
			queue.data[index-queue.head] = queue.data[index]
		}
		queue.tail = queue.tail - queue.head
		queue.head = 0
	}
	// 将新元素写入队列尾部
	queue.data[queue.tail] = element
	queue.tail++
	return nil
}

// dequeue 数据出队
func (queue *ArrayQueue) dequeue() (element int, err error) {

	// 队列为空时
	if queue.head == queue.tail {
		return 0, errors.New("队列已经空了")
	}
	queue.head++
	return queue.data[queue.head-1], nil
}
